English Version

给你一个链表的头节点 head 和一个特定值x ，请你对链表进行分隔，使得所有 小于x 的节点都出现在 大于或等于x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 

示例 2：

输入：head = [2,1], x = 2 输出：[1,2] 

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

我们创建两个链表 $left$ 和 $right$，分别用于存储小于 $x$ 的节点和大于等于 $x$ 的节点。

然后我们用两个指针 $p1$ 和 $p2$ 分别指向 $left$ 和 $right$ 的最后一个节点，初始时 $p1$ 和 $p2$ 都指向一个虚拟头节点。

接下来我们遍历链表 $head$，如果当前节点的值小于 $x$，我们就将当前节点添加到 $left$ 链表的末尾，即 $p1.next = head$，然后令 $p1 = p1.next$；否则我们就将当前节点添加到 $right$ 链表的末尾，即 $p2.next = head$，然后令 $p2 = p2.next$。

遍历结束后，我们将 $left$ 链表的尾节点指向 $right$ 链表的第一个有效节点，即 $p1.next = right.next$，然后将 $right$ 链表的尾节点指向空节点，即 $p2.next = null$。

最后我们返回 $left$ 链表的第一个有效节点。

时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution: defpartition(self, head: ListNode, x: int) ->ListNode: left, right=ListNode(0), ListNode(0) p1, p2=left, rightwhilehead: ifhead.val<x: p1.next=headp1=p1.nextelse: p2.next=headp2=p2.nexthead=head.nextp1.next=right.nextp2.next=Nonereturnleft.next

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */classSolution { publicListNodepartition(ListNodehead, intx) { ListNodeleft = newListNode(0); ListNoderight = newListNode(0); ListNodep1 = left; ListNodep2 = right; for (; head != null; head = head.next) { if (head.val < x) { p1.next = head; p1 = p1.next; } else { p2.next = head; p2 = p2.next; } } p1.next = right.next; p2.next = null; returnleft.next; } }

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };*/classSolution { public: ListNode* partition(ListNode* head, int x) { ListNode* left = newListNode(0); ListNode* right = newListNode(0); ListNode* p1 = left; ListNode* p2 = right; for (; head; head = head->next) { if (head->val < x) { p1->next = head; p1 = p1->next; } else { p2->next = head; p2 = p2->next; } } p1->next = right->next; p2->next = nullptr; return left->next; } };

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcpartition(head*ListNode, xint) *ListNode { left, right:=&ListNode{}, &ListNode{} p1, p2:=left, rightfor ; head!=nil; head=head.Next { ifhead.Val<x { p1.Next=headp1=p1.Next } else { p2.Next=headp2=p2.Next } } p1.Next=right.Nextp2.Next=nilreturnleft.Next }

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */functionpartition(head: ListNode|null,x: number): ListNode|null{const[left,right]=[newListNode(),newListNode()];let[p1,p2]=[left,right];for(;head;head=head.next){if(head.val<x){p1.next=head;p1=p1.next;}else{p2.next=head;p2=p2.next;}}p1.next=right.next;p2.next=null;returnleft.next;}

/** public class ListNode { * var val: Int * var next: ListNode? * init(_ x: Int) { * self.val = x * self.next = nil * } * } */ classSolution{func partition(_ head:ListNode?, _ x:Int)->ListNode?{letleftDummy=ListNode(0)letrightDummy=ListNode(0)varleft= leftDummy varright= rightDummy varhead= head whilelet current = head {if current.val < x { left.next = current left = left.next! }else{ right.next = current right = right.next! } head = head?.next } right.next =nil left.next = rightDummy.next return leftDummy.next }}